
<!doctype html>
<html class="theme-next use-motion theme-next-mala">
<head>
  

<meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>


<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />






  <link rel="stylesheet" type="text/css" href="/vendors/fancybox/source/jquery.fancybox.css?v=2.1.5"/>




<link rel="stylesheet" type="text/css" href="/css/main.css?v=0.4.5.1"/>


    <meta name="description" content="人皆可以為堯舜" />



  <meta name="keywords" content="数据结构与算法," />



  <link rel="alternate" href="/atom.xml" title="minichn's blog" type="application/atom+xml" />



  <link rel="shorticon icon" type="image/x-icon" href="/myimg/favicon.ico?v=0.4.5.1" />


<meta name="description" content="数据结构与算法解决的是让代码运行更快更省存储空间的问题。那如何来衡量代码的执行效率呢？这里就需要时间、空间复杂度分析。其实我们可以用“肉眼”就能看出一段代码的执行时间，那么这里我们需要引入大 O 复杂度表示法：T(n)=O(f(n))。T(n)表示代码执行的时间；n 表示数据规模的大小。f(n) 表示每行代码执行的次数总和。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。看">
<meta name="keywords" content="数据结构与算法">
<meta property="og:type" content="article">
<meta property="og:title" content=" 复杂度分析">
<meta property="og:url" content="https://cmini777.gitee.io/2019/08/13/复杂度分析/index.html">
<meta property="og:site_name" content="minichn&#39;s blog">
<meta property="og:description" content="数据结构与算法解决的是让代码运行更快更省存储空间的问题。那如何来衡量代码的执行效率呢？这里就需要时间、空间复杂度分析。其实我们可以用“肉眼”就能看出一段代码的执行时间，那么这里我们需要引入大 O 复杂度表示法：T(n)=O(f(n))。T(n)表示代码执行的时间；n 表示数据规模的大小。f(n) 表示每行代码执行的次数总和。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。看">
<meta property="og:locale" content="zh-Hans">
<meta property="og:updated_time" content="2019-08-13T06:01:18.620Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content=" 复杂度分析">
<meta name="twitter:description" content="数据结构与算法解决的是让代码运行更快更省存储空间的问题。那如何来衡量代码的执行效率呢？这里就需要时间、空间复杂度分析。其实我们可以用“肉眼”就能看出一段代码的执行时间，那么这里我们需要引入大 O 复杂度表示法：T(n)=O(f(n))。T(n)表示代码执行的时间；n 表示数据规模的大小。f(n) 表示每行代码执行的次数总和。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。看">


<script type="text/javascript" id="hexo.configuration">
  var CONFIG = {
    scheme: 'Mala',
    sidebar: 'post'
  };
</script>
<script type="text/javascript" src="/vendors/jquery/index.js?v=2.1.3"></script>

  <title>  复杂度分析 | minichn's blog </title>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  <!--[if lte IE 8]>
  <div style=' clear: both; height: 59px; padding:0 0 0 15px; position: relative;margin:0 auto;'>
    <a href="http://windows.microsoft.com/en-US/internet-explorer/products/ie/home?ocid=ie6_countdown_bannercode">
      <img src="http://7u2nvr.com1.z0.glb.clouddn.com/picouterie.jpg" border="0" height="42" width="820"
           alt="You are using an outdated browser. For a faster, safer browsing experience, upgrade for free today or use other browser ,like chrome firefox safari."
           style='margin-left:auto;margin-right:auto;display: block;'/>
    </a>
  </div>
<![endif]-->
  



  <div class="container one-column page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><h1 class="site-meta">
  <span class="logo-line-before"><i></i></span>
  <a href="/" class="brand" rel="start">
      <span class="logo">
        <i class="icon-next-logo"></i>
      </span>
      <span class="site-title">匠心沈澱</span>
  </a>
  <span class="logo-line-after"><i></i></span>
</h1>

<div class="site-nav-toggle">
  <button>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
  </button>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu menu-left">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            <i class="menu-item-icon icon-next-home"></i> <br />
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories" rel="section">
            <i class="menu-item-icon icon-next-categories"></i> <br />
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives" rel="section">
            <i class="menu-item-icon icon-next-archives"></i> <br />
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags" rel="section">
            <i class="menu-item-icon icon-next-tags"></i> <br />
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about" rel="section">
            <i class="menu-item-icon icon-next-about"></i> <br />
            关于
          </a>
        </li>
      

      
      
    </ul>
  

  
    <div class="site-search">
      
  
      <form class="site-search-form">
        <input type="text" id="local-search-input" class="st-search-input st-default-search-input" />
      </form>
      <div id="local-search-result" class="search-result-show"></div>
      <script type="text/javascript" src="/js/search.js"></script>

      


    </div>
  
</nav>

 </div>
    </header>

    
      

      
        <style type="text/css">

    .circle {
        width: 40px;
        height: 40px;
        background: #555 no-repeat;
        cursor: move;
    }

    .assist-btn {
        position: fixed;
        top: 50％;
        left: 10px;
        -moz-border-radius: 50px;
        -webkit-border-radius: 50px;
        border-radius: 50px;
        outline: none;
        border: none;
        color: #87daff;
    }

</style>

<script type="text/javascript">
    // 浮动圆点展开与收缩
    /*
    $(function () {
        var assist_box = $('.assist-box');
        $('#assist_btn').hover(function () {
            assist_box.stop().show(300);
        }, function () {
            assist_box.stop().hide(150);
        })
    });
    */  
    //浮动圆点拖动
    $(function () {
        var box = document.getElementById('assist_btn');
        box.onmousedown = function (event) {
            var e = event || window.event,
                t = e.target || e.srcElement,
                // 鼠标按下时的坐标x1,y1
                x1 = e.clientX,
                y1 = e.clientY,
                //鼠标按下时的左右偏移量
                dragLeft = this.offsetLeft,
                dragTop = this.offsetTop;

            document.onmousemove = function (event) {
                var e = event || window.event,
                    t = e.target || e.srcElement,
                    // 鼠标移动时的动态坐标
                    x2 = e.clientX,
                    y2 = e.clientY,
                    // 鼠标移动时的坐标的变化量
                    x = x2 - x1,
                    y = y2 - y1;
                box.style.left = (dragLeft + x) + 'px';
                box.style.top = (dragTop + y) + 'px';
            }

            document.onmouseup = function () {
                this.onmousemove = null;
            }
        }
    });

/*
    $whitesmoke   = #f5f5f5
    $gainsboro    = #eee
    $gray-lighter = #ddd
    $grey-light   = #ccc
    $grey         = #bbb
    $grey-dark    = #999
    $grey-dim     = #666
    $black-light  = #555
    $black-deep   = #222
    $red          = #ff2a2a
    $blue-bright  = #87daff
    $blue         = #0684bd
    $blue-deep    = #262a30
*/
    // white theme
    var body = {color: "#555", background: "white"};
    var a_tag = {color: "#222"};
    var header = { background: "#f5f5f5"};
    var logo_line_i = {background: "#222"};
    // var post_code = {background: "#eee", color: "#222"};

    function switch_theme() {
        $("body").css(body);
        $("a:not('.links-of-author-item a, .site-state-item a, .site-state-posts a, .feed-link a, .motion-element a, .post-tags a, .show-commit-cls a, #donate_board a')").css(a_tag);
        $(".header, .footer").css(header);
        $(".logo-line-before i, .logo-line-after i").css(logo_line_i);
        //$(".post code").css(post_code);
        $("#idhyt-surprise-ball #idhyt-surprise-ball-animation .drag").css(a_tag);
        $(".post-title-link, .posts-expand .post-meta, .post-comments-count, .disqus-comment-count, .post-category a, .post-nav-next a, .post-nav-item a").css(a_tag);
        
        // $("code").css({color: '#c5c8c6', background: '#1d1f21'});
        $("#assist_btn").hide(1500);
    }

    $(function () {
        $("#assist_btn").dblclick(function() {
            switch_theme();
        });
    });

</script>

<div>

    <button class="assist-btn circle" id="assist_btn" title="双击切换">
        亮
    </button>

</div>









      

    

    <main id="main" class="main">
      <div class="main-inner">
        <div id="content" class="content"> 

  <div id="posts" class="posts-expand">
    

  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
    <header class="post-header">

      
      
        <h1 class="post-title" itemprop="name headline">
          
          
            
               复杂度分析
            
          
        </h1>
      

      <div class="post-meta">
        <span class="post-time">
          发表于
          <time itemprop="dateCreated" datetime="2019-08-13T11:29:21+08:00" content="2019-08-13">
            2019-08-13
          </time>
        </span>

        
          <span class="post-category" >
            &nbsp; | &nbsp; 分类于
            
              <span itemprop="about" itemscope itemtype="https://schema.org/Thing">
                <a href="/categories/数据结构与算法/" itemprop="url" rel="index">
                  <span itemprop="name">数据结构与算法</span>
                </a>
              </span>

              
              

            
          </span>
        

        
          
        
      </div>
    </header>

    <div class="post-body">

      
      

      
        <span itemprop="articleBody"><p>数据结构与算法解决的是让代码运行更快更省存储空间的问题。那如何来衡量代码的执行效率呢？这里就需要时间、空间复杂度分析。其实我们可以用“肉眼”就能看出一段代码的执行时间，那么这里我们需要引入大 O 复杂度表示法：T(n)=O(f(n))。<br>T(n)表示代码执行的时间；n 表示数据规模的大小。f(n) 表示每行代码执行的次数总和。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。<br>看到这个概念也许觉得有点晕，没关系，上代码：<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">int cal(int n) &#123;</span><br><span class="line">  int sum = 0;</span><br><span class="line">  int i = 1;</span><br><span class="line">  <span class="keyword">for</span> (; i &lt;= n; ++i) &#123;</span><br><span class="line">    sum = sum + i;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="built_in">return</span> sum;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>假设每行代码执行的时间都一样，为 unit_time，第 2、3 行代码分别需要 1 个 unit_time 的执行时间，第 4、5 行都运行了 n 遍，所以需要 2n <em> unit_time 的执行时间，so，上面整段代码执行时间是(2n+2) </em> unit_time。可以看出来，所有代码的执行时间 T(n) 与每行代码的执行次数成正比。套上公式，那就是T(n) = O(2n+2)，这就是大 O 时间复杂度表示法。<br>它并不代表代码执行的具体时间，但是它能表示出代码执行时间的变化趋势，我们可以把这个叫做渐进时间复杂度（简称：时间复杂度）。既然它表示的是代码执行时间的变化趋势，那么我们可以把公式中的低阶、常量、系数三部分忽略掉，我们只需要记录一个最大量级就可以了，so，上面这段代码可以标记为T(n) = O(n)。<br>是不是有点感觉了，再来一段代码练练手：<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">int cal(int n) &#123;</span><br><span class="line">  int sum = 0;</span><br><span class="line">  int i = 1;</span><br><span class="line">  int j = 1;</span><br><span class="line">  <span class="keyword">for</span> (; i &lt;= n; ++i) &#123;</span><br><span class="line">    j = 1;</span><br><span class="line">    <span class="keyword">for</span> (; j &lt;= n; ++j) &#123;</span><br><span class="line">      sum = sum +  i * j;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>第 2、3、4 行代码分别需要 1 个 unit_time 的执行时间，第 5、6 行都运行了 n 遍，所以需要 2n <em> unit_time 的执行时间，第 7、8 行代码循环执行次数为 n^2，所以需要 2 </em> n^2 <em> unit_time 的执行时间，so，上面整段代码执行时间是(2 </em> n^2+2n+3) <em> unit_time。套上公式，那就是T(n) = O(2 </em> n^2+2n+3)，so，上面这段代码可以标记为T(n) = O(n^2)。</p>
<h1 id="时间复杂度分析方法"><a href="#时间复杂度分析方法" class="headerlink" title="时间复杂度分析方法"></a>时间复杂度分析方法</h1><p>1、只关注循环执行次数最多的一段代码<br>上面的那两个举例，第一段代码总的时间复杂度就是 O(n)，第二段代码就是O(n^2)<br>2、加法法则：总复杂度等于量级最大的那段代码的复杂度<br>如果 T1(n)=O(f(n))，T2(n)=O(g(n))，那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n)))=O(max(f(n), g(n)))。<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">int cal(int n) &#123;</span><br><span class="line">   int sum_1 = 0;</span><br><span class="line">   int p = 1;</span><br><span class="line">   <span class="keyword">for</span> (; p &lt; 100; ++p) &#123;</span><br><span class="line">     sum_1 = sum_1 + p;</span><br><span class="line">   &#125;</span><br><span class="line"></span><br><span class="line">   int sum_2 = 0;</span><br><span class="line">   int q = 1;</span><br><span class="line">   <span class="keyword">for</span> (; q &lt; n; ++q) &#123;</span><br><span class="line">     sum_2 = sum_2 + q;</span><br><span class="line">   &#125;</span><br><span class="line"> </span><br><span class="line">   int sum_3 = 0;</span><br><span class="line">   int i = 1;</span><br><span class="line">   int j = 1;</span><br><span class="line">   <span class="keyword">for</span> (; i &lt;= n; ++i) &#123;</span><br><span class="line">     j = 1; </span><br><span class="line">     <span class="keyword">for</span> (; j &lt;= n; ++j) &#123;</span><br><span class="line">       sum_3 = sum_3 +  i * j;</span><br><span class="line">     &#125;</span><br><span class="line">   &#125;</span><br><span class="line"> </span><br><span class="line">   <span class="built_in">return</span> sum_1 + sum_2 + sum_3;</span><br><span class="line"> &#125;</span><br></pre></td></tr></table></figure></p>
<p>综合这三段代码的时间复杂度，我们取其中最大的量级，so，上面这段代码复杂度为O(n^2)。<br>3、乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积<br>如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n) × T2(n)=O(f(n)) × O(g(n))=O(f(n) × g(n))。<br>假设 T1(n) = O(n)，T2(n) = O(n^2)，则 T1(n) × T2(n) = O(n^3)。</p>
<h1 id="常用的复杂度级别"><a href="#常用的复杂度级别" class="headerlink" title="常用的复杂度级别"></a>常用的复杂度级别</h1><p>多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，<br>O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶）<br>非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，<br>O(2^n)（指数阶）、O(n!)（阶乘阶）<br>例如：<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">int i = 8;</span><br><span class="line">int j = 6;</span><br><span class="line">int sum = i + j;</span><br></pre></td></tr></table></figure></p>
<p>上面这段代码的时间复杂度是O(1)。总结：只要代码的执行时间不随 n 的增大而增长，我们都可以称之为常数阶，即时间复杂度是O(1)。<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">i=1;</span><br><span class="line"><span class="keyword">while</span> (i &lt;= n)  &#123;</span><br><span class="line">  i = i * 2;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>变量 i 的值从 1 开始取，每循环一次就乘以 2，当大于 n 时，循环结束。<br>这里就是等比数列，例如2^0，2^1，2^2，……，2^x。<br>2^x=n 求解 x，x=log2n，所以上面这段代码的时间复杂度为O(log2n)<br><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">i=1;</span><br><span class="line"><span class="keyword">while</span> (i &lt;= n)  &#123;</span><br><span class="line">  i = i * 3;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>上面这段代码的时间复杂度为O(log3n)<br>不管是以 2 为底、以 3 为底、以几为底，我们可以把所有对数阶的时间复杂度都记为 O(logn)。</p>
<h1 id="空间复杂度分析"><a href="#空间复杂度分析" class="headerlink" title="空间复杂度分析"></a>空间复杂度分析</h1><p>空间复杂度全称就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。<br>就是看代码有没有占有更多的空间，跟时间复杂度分析一样，低阶、常量阶跟数据规模n没有关系，所以可以忽略，例如申请了一个变量i，我们就可以忽略，但如果申请了一个大小为n的数组，我们就可以将这个空间复杂度表示为O(n)。</p>
</span>
      
    </div>

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/数据结构与算法/" rel="tag">#数据结构与算法</a>
          
        </div>
      

      
        <div class="post-nav">
          <div class="post-nav-prev post-nav-item">
            
              <a href="/2019/08/13/React整合ECharts/" rel="prev">React整合ECharts</a>
            
          </div>

          <div class="post-nav-next post-nav-item">
            
              <a href="/2019/08/09/linux下使用nginx配置https出错/" rel="next">linux下使用nginx配置https出错:</a>
            
          </div>
        </div>
      

      
      
    </footer>
  </article>



    <div>
      
    </div>

    <div class="post-spread">
      
    </div>
  </div>

 </div>

        

        
          <div class="comments" id="comments">
            
          </div>
        
      </div>

      
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" src="/images/default_avatar.jpg" alt="minichn" itemprop="image"/>
          <p class="site-author-name" itemprop="name">minichn</p>
        </div>
        <p class="site-description motion-element" itemprop="description">人皆可以為堯舜</p>
        <nav class="site-state motion-element">
          <div class="site-state-item site-state-posts">
            <a href="/archives">
              <span class="site-state-item-count">14</span>
              <span class="site-state-item-name">日志</span>
            </a>
          </div>

          <div class="site-state-item site-state-categories">
            <a href="/categories">
              <span class="site-state-item-count">12</span>
              <span class="site-state-item-name">分类</span>
              </a>
          </div>

          <div class="site-state-item site-state-tags">
            <a href="/tags">
              <span class="site-state-item-count">16</span>
              <span class="site-state-item-name">标签</span>
              </a>
          </div>

        </nav>

        
          <!-- <div class="feed-link motion-element">
            <a href="/atom.xml" rel="alternate">
              <i class="menu-item-icon icon-next-feed"></i>
              RSS
            </a>
          </div> -->
        

        <div class="links-of-author motion-element">
          
            
              <span class="links-of-author-item">
                <a href="https://github.com/CMINI777" target="_blank">GitHub</a>
              </span>
            
              <span class="links-of-author-item">
                <a href="https://gitee.com/CMINI777" target="_blank">Gitee</a>
              </span>
            
              <span class="links-of-author-item">
                <a href="https://www.zhihu.com/people/chnguo/activities" target="_blank">ZhiHu</a>
              </span>
            
              <span class="links-of-author-item">
                <a href="https://cmini777.gitee.io/about/" target="_blank">MiniCHN</a>
              </span>
            
          
        </div>

        <div class="links-of-friendly motion-element">
          
            <p class="site-author-name">友情链接</p>
            
              <span class="links-of-author-item">
              <a href="http://blog.idhyt.com/about/" target="_blank">idhyt</a>
              </span>
            
              <span class="links-of-author-item">
              <a href="https://blog.guxiangfly.cn/" target="_blank">guxiangfly</a>
              </span>
            
          
        </div>

        
        
          <div class="cc-license motion-element" itemprop="license">
            <a href="http://creativecommons.org/licenses/by-nc-sa/4.0" class="cc-opacity" target="_blank">
              <img src="/images/cc-by-nc-sa.svg" alt="Creative Commons" />
            </a>
          </div>
        

      </section>

      
        <section class="post-toc-wrap sidebar-panel-active">
          <div class="post-toc-indicator-top post-toc-indicator"></div>
          <div class="post-toc">
            
            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#时间复杂度分析方法"><span class="nav-number">1.</span> <span class="nav-text">时间复杂度分析方法</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#常用的复杂度级别"><span class="nav-number">2.</span> <span class="nav-text">常用的复杂度级别</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#空间复杂度分析"><span class="nav-number">3.</span> <span class="nav-text">空间复杂度分析</span></a></li></ol></div>
            
          </div>
          <div class="post-toc-indicator-bottom post-toc-indicator"></div>
        </section>
      

    </div>
  </aside>


    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner"> <div class="copyright" >
  
  &copy; &nbsp;  2018 - 
  <span itemprop="copyrightYear">2019
  </span>
  <span class="with-love">
    <i class="icon-next-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">minichn
  </span>
</div>

<div class="powered-by">
  Powered by <a class="theme-link" href="http://hexo.io">Hexo</a>
</div>

<div class="theme-info">
  Theme by <a class="theme-link" href="https://cmini777.gitee.io/">minichn</a>.<a class="theme-link" href="https://gitee.com/CMINI777/next-minichn">next-minichn</a>
</div>

<!-- busuanzi -->



 </div>
    </footer>

    <div class="back-to-top"></div>
  </div>

  
  
  
    
    

  


  
  
  <script type="text/javascript" src="/vendors/fancybox/source/jquery.fancybox.pack.js"></script>
  <script type="text/javascript" src="/js/fancy-box.js?v=0.4.5.1"></script>


  <script type="text/javascript" src="/js/helpers.js?v=0.4.5.1"></script>
  

  <script type="text/javascript" src="/vendors/velocity/velocity.min.js"></script>
  <script type="text/javascript" src="/vendors/velocity/velocity.ui.min.js"></script>

  <script type="text/javascript" src="/js/motion_global.js?v=0.4.5.1" id="motion.global"></script>




  <script type="text/javascript" src="/js/nav-toggle.js?v=0.4.5.1"></script>
  <script type="text/javascript" src="/vendors/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  
<script type="text/javascript" src="/js/bootstrap.scrollspy.js?v=0.4.5.1" id="bootstrap.scrollspy.custom"></script>


<script type="text/javascript" id="sidebar.toc.highlight">
  $(document).ready(function () {
    var tocSelector = '.post-toc';
    var $tocSelector = $(tocSelector);
    var activeCurrentSelector = '.active-current';

    $tocSelector
      .on('activate.bs.scrollspy', function () {
        var $currentActiveElement = $(tocSelector + ' .active').last();

        removeCurrentActiveClass();
        $currentActiveElement.addClass('active-current');

        $tocSelector[0].scrollTop = $currentActiveElement.position().top;
      })
      .on('clear.bs.scrollspy', function () {
        removeCurrentActiveClass();
      });

    function removeCurrentActiveClass () {
      $(tocSelector + ' ' + activeCurrentSelector)
        .removeClass(activeCurrentSelector.substring(1));
    }

    function processTOC () {
      getTOCMaxHeight();
      toggleTOCOverflowIndicators();
    }

    function getTOCMaxHeight () {
      var height = $('.sidebar').height() -
                   $tocSelector.position().top -
                   $('.post-toc-indicator-bottom').height();

      $tocSelector.css('height', height);

      return height;
    }

    function toggleTOCOverflowIndicators () {
      tocOverflowIndicator(
        '.post-toc-indicator-top',
        $tocSelector.scrollTop() > 0 ? 'show' : 'hide'
      );

      tocOverflowIndicator(
        '.post-toc-indicator-bottom',
        $tocSelector.scrollTop() >= $tocSelector.find('ol').height() - $tocSelector.height() ? 'hide' : 'show'
      )
    }

    $(document).on('sidebar.motion.complete', function () {
      processTOC();
    });

    $('body').scrollspy({ target: tocSelector });
    $(window).on('resize', function () {
      if ( $('.sidebar').hasClass('sidebar-active') ) {
        processTOC();
      }
    });

    onScroll($tocSelector);

    function onScroll (element) {
      element.on('mousewheel DOMMouseScroll', function (event) {
          var oe = event.originalEvent;
          var delta = oe.wheelDelta || -oe.detail;

          this.scrollTop += ( delta < 0 ? 1 : -1 ) * 30;
          event.preventDefault();

          toggleTOCOverflowIndicators();
      });
    }

    function tocOverflowIndicator (indicator, action) {
      var $indicator = $(indicator);
      var opacity = action === 'show' ? 0.4 : 0;
      $indicator.velocity ?
        $indicator.velocity('stop').velocity({
          opacity: opacity
        }, { duration: 100 }) :
        $indicator.stop().animate({
          opacity: opacity
        }, 100);
    }

  });
</script>

<script type="text/javascript" id="sidebar.nav">
  $(document).ready(function () {
    var html = $('html');
    var TAB_ANIMATE_DURATION = 200;
    var hasVelocity = $.isFunction(html.velocity);

    $('.sidebar-nav li').on('click', function () {
      var item = $(this);
      var activeTabClassName = 'sidebar-nav-active';
      var activePanelClassName = 'sidebar-panel-active';
      if (item.hasClass(activeTabClassName)) {
        return;
      }

      var currentTarget = $('.' + activePanelClassName);
      var target = $('.' + item.data('target'));

      hasVelocity ?
        currentTarget.velocity('transition.slideUpOut', TAB_ANIMATE_DURATION, function () {
          target
            .velocity('stop')
            .velocity('transition.slideDownIn', TAB_ANIMATE_DURATION)
            .addClass(activePanelClassName);
        }) :
        currentTarget.animate({ opacity: 0 }, TAB_ANIMATE_DURATION, function () {
          currentTarget.hide();
          target
            .stop()
            .css({'opacity': 0, 'display': 'block'})
            .animate({ opacity: 1 }, TAB_ANIMATE_DURATION, function () {
              currentTarget.removeClass(activePanelClassName);
              target.addClass(activePanelClassName);
            });
        });

      item.siblings().removeClass(activeTabClassName);
      item.addClass(activeTabClassName);
    });

    $('.post-toc a').on('click', function (e) {
      e.preventDefault();
      var targetSelector = escapeSelector(this.getAttribute('href'));
      var offset = $(targetSelector).offset().top;
      hasVelocity ?
        html.velocity('stop').velocity('scroll', {
          offset: offset  + 'px',
          mobileHA: false
        }) :
        $('html, body').stop().animate({
          scrollTop: offset
        }, 500);
    });

    // Expand sidebar on post detail page by default, when post has a toc.
    var $tocContent = $('.post-toc-content');
    if (isDesktop() && CONFIG.sidebar === 'post') {
      if ($tocContent.length > 0 && $tocContent.html().trim().length > 0) {
        displaySidebar();
      }
    }
  });
</script>



  <script type="text/javascript">
    $(document).ready(function () {
      if (CONFIG.sidebar === 'always') {
        displaySidebar();
      }
      if (isMobile()) {
        FastClick.attach(document.body);
      }
    });
  </script>

  

  
  

  
  <script type="text/javascript" src="/js/lazyload.js"></script>
  <script type="text/javascript">
    $(function () {
      $("#posts").find('img').lazyload({
        placeholder: "/images/loading.gif",
        effect: "fadeIn"
      });
    });
  </script>
</body>
</html>
